Multi-threaded computer systems are computers with operating systems that allow the sharing of system resources among multiple threads. Multi-threaded computer systems increase computer performance by allowing multiple streams of instructions to be processed by the computer's central processing unit (CPU) at the same time. Operating systems differ in both the extent and manner in which they support multi-threading. Accordingly, the meaning and attributes of threads differ between operating systems. Generally, a thread is an independent, schedulable, stream of instructions belonging to a particular program. As a schedulable entity, a thread has only those properties that are required to ensure its independent flow of control. These properties include a stack, scheduling properties such as policy and priority, a set of pending and blocked signals, and thread specific data.
Multi-threaded computer programs require support from the operating system or programming language. Most modern operating systems provide libraries so that programmers can create multi-threaded applications. Some programming languages, in particular, object-oriented languages such as Java and Ada, build support for threads into the programming language. For example, the Java programming language provides the class Thread that models threads and allows the creation of multi-threaded programs. Program development tools, application subsystems, and middleware also provide thread management capabilities.
Traditionally, thread implementations provided by operating systems differed significantly from one another, making it difficult to develop portable multi-threaded programs that can be used on different systems without recoding. One solution to this problem was the creation of a set of standardized operating system interfaces known as POSIX (Portable Operating System Interface). The POSIX.4a specification provides a set of Application Program Interfaces (APIs) that allow a C programmer to include thread support in their programs. Thread implementations adhering to this standard are referred to as POSIX threads or Pthreads. The problem with the POSIX standard is that it was defined for the C programming language only. Efforts to define the POSIX standard for other languages are still in progress, and while programmers in some programming languages can use the POSIX standard by using wrappers around C function calls, the POSIX standard has not been uniformly adopted and proprietary versions of threads persist. Known proprietary thread implementations, by way of example, are those of IBM's AIX, Sun's Solaris and Microsoft's Windows NT systems.
Many computer systems cannot execute multiple threads simultaneously due to competition for CPU resources among the multiple threads. Most desktop computers execute threads in a concurrent interwoven fashion, overlapped in time. As a schedulable entity, each thread can be allocated a number of CPU cycles by the operating system. For this reason, a thread is sometimes referred to as an independent flow of control. The amount of “time” each thread is given control of the CPU occurs so fast and in such rapid succession that it resembles simultaneous execution. The execution of one program instruction may require the execution of several machine instructions. With multiple threads allocated among a fixed number of CPU cycles by the operating system, a thread may not complete the execution of a program instruction before relinquishing control of the CPU to another thread. When a thread resumes processing, it often requires access to data it was using when it relinquished control. However, multi-threaded programs use local variables which are dynamically allocated on the stack. Consequently, threads do not hold static data over successive calls or return a pointer to static data.
Threads can be generated by different programs or by a single program with sufficient parallelism. In a multi-threaded computing environment, the multiple threads may belong to a single program, or each thread may belong to a different program, or several threads may belong to one program with other threads belonging to another program.
During the operation of a program, the operating system may create processes or tasks to execute program instructions. A single program may have multiple processes in execution, and each process can have multiple threads. Illustratively, a process in the UNIX environment contains information about program resources and the program execution state, including: process ID, environment, working directory, program instructions, and registers. A process also provides a common address space and common system resources, including: file descriptors, signal actions, shared libraries and inter-process communication tools (such as message queues, semaphores, and shared memory). A thread exists within a process and uses the process resources.
All threads within a process share system resources and operate in the same address space. Static variables declared within a computer program have a static storage location. Accordingly, references to a static variable from any thread will refer to the memory location allocated to that variable. Multiple copies of static variables location are not created as they may be with other variables types. The value of a static variable will always be the last value written to its memory. One of the primary advantages of static variables is that their values persist between references, and will exist for as long as the program operates. In a multi-threaded program, static variables allow a thread to resume execution of its instructions and access data it was using before it relinquished control of the CPU to another thread.
One of the primary difficulties that result from using static variables in multi-threaded computer programs is that changes to a static variable made by one thread will be seen by all other threads operating within the same process. Multiple threads cannot use static variables separately because other threads within the process can overwrite the values stored at the variable memory location. Thus, the development of multi-threaded programs using static variables often requires explicit thread harmonization by the programmer. Another problem is that threads within the same process must use unique static variable IDs to avoid reading or writing to the location of another static variable. This also requires thread harmonization by the programmer.
One known solution to the problems created by using static variables in multi-threaded computer programs is thread-static data variables. Thread-static variables are static variables that are accessed and used separately by each thread. Thread-static variables are local to the thread to which they relate. Most computer languages do not provide thread-static data variable so computer programmers have been forced to develop their own thread-static data implementations. The primary disadvantage of most thread-static data implementations is the high cost of system resources. Known thread-static data implementations typically require 50 CPU instructions or more.
In most thread implementations, each thread is allocated a block of virtual memory, known as a stack, for use as temporary storage of local data and other information during its execution.
According to one known implementation, thread-static data is allocated on the stack by declaring it as an auto variable in a function executed by each thread accessing the data. To access the data, a thread must specify the address of the thread-static data using a functional argument from the thread's calling function to the called function. The primary disadvantage with this approach is that the thread-static data cannot be accessed directly, so the program becomes complicated and the execution efficiency is lowered. Another disadvantage with this approach is that it requires storing the address of the thread-static data on the stack.
Other known implementations involve the use of thread identifiers or IDs. According to one implementation, a global array is declared with as many elements as there are threads. Each thread is assigned a unique thread ID. Threads access the thread-static data from the global array using their respective thread IDs. One problem with this approach is that not all operating systems support thread IDs. Where thread IDs are not supported, it is necessary to support thread IDs within the program, thereby lowering the execution efficiency. Even when thread IDs are supported by the operating system, this implementation does not work where the number of threads changes dynamically because the maximum number of threads supported is fixed by the size of the global array.
One known solution to this problem involves hashing the thread IDs. Typically, such implementations obtain the current thread ID and use it as an index into a hash table that would provide the address of the thread's static data region. The primary disadvantage of this approach is that obtaining the current thread ID often involves the use of a system call. Systems calls are very expensive in terms of resource utilization and lower system performance. Furthermore, a hash table look up can require 10's of CPU instructions. For example, 50 CPU instructions or more may be required to access the static data of the current thread.
Another known implementation involves registering pointers to thread-static data. According to one implementation, thread-static data to be used by each one of the multiple threads is detected and allocated to each thread's respective stack. Pointers are then registered to indicate the top and base addresses of the thread-static data region in the stack for each one of the multiple threads. Access instructions indicate variable offsets within the thread-static data region of each stack. Thread-static data variables are then accessed using the pointer to the base address of the thread-static data region and the position of the data variable within this region as indicated by the access instructions. This implementation allows thread-static data to be declared globally without thread IDs, and can accommodate changes in the number of threads which result from the creation and termination of threads. This approach is more efficient than those previously described because it requires less complicated programming and can access data directly. The primary limitation of this method is that most modem operating systems do not generally allow application programs to devote CPU registers to specific usages.
Accordingly, in view of the shortcomings associated with existing thread-static data implementations, there remains a need for an efficient thread-static data implementation that can be used on most modem operating systems.